{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Equal Tree Partition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkEqualTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #均匀树划分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵有 <code>n</code> 个结点的二叉树，你的任务是检查是否可以通过去掉树上的一条边将树分成两棵，且这两棵树结点之和相等。</p>\n",
    "\n",
    "<p><strong>样例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong>     \n",
    "    5\n",
    "   / \\\n",
    "  10 10\n",
    "    /  \\\n",
    "   2   3\n",
    "\n",
    "<strong>输出:</strong> True\n",
    "<strong>解释:</strong> \n",
    "    5\n",
    "   / \n",
    "  10\n",
    "      \n",
    "和: 15\n",
    "\n",
    "   10\n",
    "  /  \\\n",
    " 2    3\n",
    "\n",
    "和: 15\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>样例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong>     \n",
    "    1\n",
    "   / \\\n",
    "  2  10\n",
    "    /  \\\n",
    "   2   20\n",
    "\n",
    "<strong>输出:</strong> False\n",
    "<strong>解释:</strong> 无法通过移除一条树边将这棵树划分成结点之和相等的两棵子树。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注释 :</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>树上结点的权值范围 [-100000, 100000]。</li>\n",
    "\t<li>1 &lt;= n &lt;= 10000</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [equal-tree-partition](https://leetcode.cn/problems/equal-tree-partition/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [equal-tree-partition](https://leetcode.cn/problems/equal-tree-partition/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,10,10,null,null,2,3]', '[1,2,10,null,null,2,20]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def getSum(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return node.val + getSum(node.left) + getSum(node.right)\n",
    "        \n",
    "        def traverseTree(node, halfSum):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            subtreeSum = node.val + traverseTree(node.left, halfSum) + traverseTree(node.right, halfSum)\n",
    "            if node != root and subtreeSum == halfSum:\n",
    "                self.found = True\n",
    "            return subtreeSum\n",
    "        \n",
    "        total_sum = getSum(root)\n",
    "        if total_sum % 2:\n",
    "            return False\n",
    "\n",
    "        halfSum = total_sum / 2\n",
    "        self.found = False\n",
    "        \n",
    "        traverseTree(root, halfSum)\n",
    "\n",
    "        return self.found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def sumTree(node):\n",
    "            if not node: return 0\n",
    "            return sumTree(node.left) + sumTree(node.right) + node.val\n",
    "        \n",
    "        tree_sum = sumTree(root)\n",
    "        if tree_sum % 2 == 1: return False\n",
    "        target = tree_sum // 2\n",
    "\n",
    "        def split(node, target):\n",
    "            if not node: return False\n",
    "            if sumTree(node) == target: return True\n",
    "            return split(node.left, target) or split(node.right, target)\n",
    "\n",
    "        return split(root.left, target) or split(root.right, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        que = Counter()\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            res = l + r + node.val\n",
    "            que[node] = res \n",
    "            return res\n",
    "\n",
    "        tot = dfs(root)\n",
    "        if tot % 2:\n",
    "            return False \n",
    "        for k, v in que.items():\n",
    "            if v == tot // 2 and k != root:\n",
    "                return True \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        que = Counter()\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            res = l + r + node.val\n",
    "            que[node] = res \n",
    "            return res\n",
    "\n",
    "        tot = dfs(root)\n",
    "        if tot % 2:\n",
    "            return False \n",
    "        for k, v in que.items():\n",
    "            if v == tot // 2 and k != root:\n",
    "                return True \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        m = {}\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            m[node] = l + r + node.val\n",
    "            return m[node]\n",
    "        \n",
    "        dfs(root)\n",
    "        # print(m)\n",
    "        if m[root] % 2 != 0:\n",
    "            return False\n",
    "        tar = m[root] >> 1\n",
    "        # print(m)\n",
    "        for k, v in m.items():\n",
    "            if k != root and v == tar:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        sums = []\n",
    "\n",
    "        def dfstotal(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            total = node.val + dfstotal(node.left) + dfstotal(node.right)\n",
    "            sums.append(total)\n",
    "            return total\n",
    "\n",
    "        total_sum = dfstotal(root)\n",
    "        sums.pop()  # 删除最后一个元素，即整棵树的总和\n",
    "\n",
    "        if total_sum % 2 != 0:\n",
    "            return False  # 如果总和是奇数，直接返回False\n",
    "        \n",
    "        half_sum = total_sum // 2\n",
    "        return half_sum in sums  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        sum=[]\n",
    "        def dfstotal(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l=dfstotal(root.left)\n",
    "            r=dfstotal(root.right)\n",
    "            total=l+root.val+r\n",
    "            sum.append(total)\n",
    "            return total\n",
    "        totalsum=dfstotal(root)\n",
    "        sum.pop()\n",
    "        if totalsum%2!=0:\n",
    "            return False\n",
    "        half=totalsum//2 \n",
    "        return half in sum\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        visited = []\n",
    "\n",
    "        def cal(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left = cal(root.left)\n",
    "            right = cal(root.right)\n",
    "            if root.left:\n",
    "                visited.append(left)\n",
    "            if root.right:\n",
    "                visited.append(right)\n",
    "            return left + right + root.val\n",
    "\n",
    "        tot = cal(root)\n",
    "        if tot % 2 == 0 and tot // 2 in visited:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        flag = [False]\n",
    "\n",
    "        def cal(root, tot):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left = cal(root.left, tot)\n",
    "            right = cal(root.right, tot)\n",
    "            if root.left is not None and left * 2 == tot:\n",
    "                flag[0] = True\n",
    "            if root.right is not None and right * 2 == tot:\n",
    "                flag[0] = True\n",
    "            return left + right + root.val\n",
    "\n",
    "        def cal_tot(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left = cal_tot(root.left)\n",
    "            right = cal_tot(root.right)\n",
    "            return left + right + root.val\n",
    "\n",
    "        tot = cal_tot(root)\n",
    "        if tot % 2 == 1:\n",
    "            return False\n",
    "        cal(root, tot)\n",
    "        return flag[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        m = {}\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            m[node] = l + r + node.val\n",
    "            return m[node]\n",
    "        \n",
    "        dfs(root)\n",
    "        # print(m)\n",
    "        if m[root] % 2 != 0:\n",
    "            return False\n",
    "        tar = m[root] >> 1\n",
    "        # print(m)\n",
    "        del m[root]\n",
    "        return any(v == tar for v in m.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.subTreeSum = set()\n",
    "\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        treeSum = root.val + self.sum(root.left) + self.sum(root.right)\n",
    "        if treeSum % 2 != 0:\n",
    "            return False\n",
    "\n",
    "        return treeSum // 2 in self.subTreeSum\n",
    "\n",
    "\n",
    "    def sum(self,root):\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        leftsum = self.sum(root.left)\n",
    "        rightsum = self.sum(root.right)\n",
    "        rootsum = leftsum + rightsum + root.val\n",
    "        self.subTreeSum.add(rootsum)\n",
    "        return rootsum\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        s = set()\n",
    "        def dfs(u):\n",
    "            if not u: return 0\n",
    "            v = dfs(u.left) + dfs(u.right) + u.val\n",
    "            if u != root:\n",
    "                s.add(v)\n",
    "            return v\n",
    "        r = dfs(root)\n",
    "        return r / 2 in s\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        s=set()\n",
    "        def dfs(node):\n",
    "            n=node.val\n",
    "            if node.left:\n",
    "                n+=dfs(node.left)\n",
    "            if node.right:\n",
    "                n+=dfs(node.right)\n",
    "            if node!=root:\n",
    "                s.add(n)\n",
    "            return n\n",
    "        now=dfs(root)\n",
    "        if now%2==1:\n",
    "            return False\n",
    "        return now//2 in s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        visited = set()\n",
    "\n",
    "        def cal(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left = cal(root.left)\n",
    "            right = cal(root.right)\n",
    "            if root.left:\n",
    "                visited.add(left)\n",
    "            if root.right:\n",
    "                visited.add(right)\n",
    "            return left + right + root.val\n",
    "\n",
    "        tot = cal(root)\n",
    "        if tot % 2 == 0 and tot // 2 in visited:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 一边遍历一边存储子树和\n",
    "        self.sum_set = set()\n",
    "        s = self.get_sum(root.left) + self.get_sum(root.right) + root.val\n",
    "        return s / 2 in self.sum_set \n",
    "\n",
    "    def get_sum(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        left = self.get_sum(root.left)\n",
    "        right = self.get_sum(root.right)\n",
    "        res = root.val + left + right\n",
    "        self.sum_set.add(res)\n",
    "        return res \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        self.subTreeSum = []\n",
    "\n",
    "        TreeSum = self.treeSum(root)\n",
    "\n",
    "        return TreeSum / 2 in self.subTreeSum[:-1]\n",
    "\n",
    "    def treeSum(self, root):\n",
    "        if root is None:\n",
    "            return 0 \n",
    "\n",
    "        left_sum = self.treeSum(root.left)\n",
    "        right_sum = self.treeSum(root.right)\n",
    "\n",
    "        tree_sum = left_sum + right_sum + root.val \n",
    "\n",
    "        self.subTreeSum.append(tree_sum)\n",
    "\n",
    "        return tree_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        my_set = set()\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return 0\n",
    "            temp = node.val + dfs(node.left) + dfs(node.right)\n",
    "            if node != root:\n",
    "                my_set.add(temp)\n",
    "            return temp\n",
    "        return dfs(root) / 2 in my_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        self.subTreeSum = []\n",
    "\n",
    "        TreeSum = self.treeSum(root.left) + self.treeSum(root.right) + root.val\n",
    "\n",
    "        return TreeSum / 2 in self.subTreeSum\n",
    "\n",
    "    def treeSum(self, root):\n",
    "        if root is None:\n",
    "            return 0 \n",
    "\n",
    "        left_sum = self.treeSum(root.left)\n",
    "        right_sum = self.treeSum(root.right)\n",
    "\n",
    "        tree_sum = left_sum + right_sum + root.val \n",
    "\n",
    "        self.subTreeSum.append(tree_sum)\n",
    "\n",
    "        return tree_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        d = set()\n",
    "\n",
    "        def dfs(root):\n",
    "            left = right = 0\n",
    "            if root.left:\n",
    "                left = dfs(root.left)\n",
    "                d.add(left)\n",
    "            if root.right:\n",
    "                right = dfs(root.right)\n",
    "                d.add(right)\n",
    "            return left + right + root.val\n",
    "        \n",
    "        total = dfs(root)\n",
    "        if total == 0:\n",
    "            return 0 in d\n",
    "        return total % 2 == 0 and total // 2 in d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        self.sum_set = set()\n",
    "        self.root = root\n",
    "        s = self.get_sum(root)\n",
    "        return s / 2 in self.sum_set \n",
    "\n",
    "    def get_sum(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        left = self.get_sum(root.left)\n",
    "        right = self.get_sum(root.right)\n",
    "        res = root.val + left + right\n",
    "        if root != self.root:\n",
    "            self.sum_set.add(res)\n",
    "        return res \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        s = set()\n",
    "        def dfs(u):\n",
    "            if not u: return 0\n",
    "            v = dfs(u.left) + dfs(u.right) + u.val\n",
    "            if u != root:\n",
    "                s.add(v)\n",
    "            return v\n",
    "        r = dfs(root)\n",
    "        return r / 2 in s\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        d = set()\n",
    "\n",
    "        def dfs(root):\n",
    "            left = right = 0\n",
    "            if root.left:\n",
    "                left = dfs(root.left)\n",
    "                d.add(left)\n",
    "            if root.right:\n",
    "                right = dfs(root.right)\n",
    "                d.add(right)\n",
    "            return left + right + root.val\n",
    "        \n",
    "        total = dfs(root)\n",
    "        return total % 2 == 0 and total // 2 in d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        d = set()\n",
    "\n",
    "        def dfs(root):\n",
    "            left = right = 0\n",
    "            if root.left:\n",
    "                left = dfs(root.left)\n",
    "                d.add(left)\n",
    "            if root.right:\n",
    "                right = dfs(root.right)\n",
    "                d.add(right)\n",
    "            return left + right + root.val\n",
    "        \n",
    "        total = dfs(root)\n",
    "        return total % 2 == 0 and total // 2 in d"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
